package com.ohc.leetcode.链表;

import java.util.ArrayList;
import java.util.HashSet;

/**
 * https://leetcode.cn/problems/remove-duplicate-node-lcci/
 * 2022年6月19日11:32:21
 * <p>
 * 过
 */
public class 面试题0201移除重复节点 {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public static ListNode removeDuplicateNodes(ListNode head) {
        ListNode dump = new ListNode(0);
        dump.next = head;
        ListNode temp = dump;
        HashSet<Integer> set = new HashSet<>();
        while (temp != null && temp.next != null) {
            if (!set.contains(temp.next.val)) {
                set.add(temp.next.val);
            } else {
                temp.next = temp.next.next; // 删除中间结点
            }
            temp = temp.next;
        }
//        [1, 2, 3, 3, 2, 1]
        set.forEach(e -> {
            System.out.println("e = " + e);
        });
        return dump;
    }

    /**
     * 题解学习，暴力法
     *
     * @param head
     * @return
     */
    public static ListNode removeDuplicateNodes2(ListNode head) {
        ListNode out = head;
        ListNode in = head;
        while (out != null) {
            while (in.next != null) {
                if (in.next.val != out.val) { // 没找到移动指针
                    in = in.next;
                } else { // 找到了
                    in.next = in.next.next; // 删除中间节点
                }
            }
            out = out.next;
        }
        return head;
    }

    public static void main(String[] args) {
//        removeDuplicateNodes(null);
//            new ArrayList<>()
    }
}
